資料結構的定義

資料 & 資訊

• 資料 ( Data )：尚未被處理過的原始文字、數字、符號、圖形
• 資訊 ( Information )：經過處理 ( Processing ) 的資料；處理的方式可能是整理、歸納、分析

資料的特性

依照計算機的儲存跟使用特性，資料分為兩大類，可拿來做運算的數值資料 ( Numeric Data ) ，跟不能拿來當作運算子 ( Operator ) 的文數資料 ( Alphanumeric Data )。

若依照資料在計算機的程式語言中的存在層次做區分，會被分成三種型態：

1. 基本資料型態 / 純量資料型態 ( Primitive Data Type / Scalar Data Type )：無法用其他型態定義的資料型態，如 C++ 中的 int 、float 、char 、Boolean
2. 結構化資料型態 / 虛擬資料型態 ( Structured Data Type / Virtual Data Type ) ：比基本資料型態高一層的資料型態，如 string、array、pointer 、 list 、 file
3. 抽象資料型態 ( Abstract Data Type, ADT )： 定義資料型態的行為或操作，但不涉及具體該如何實現。可以理解 ADT 只在乎「什麼 ( What ) 」東西可以做，不過不在意該「怎麼 ( How ) 」做。像是 Queue 的先進先出的資料運作方式就是一種 ADT 模式

資料結構的應用

• 樹狀結構：非線性資料結構，用於 Unix 作業系統、平面繪圖、遊戲設計
• 最短路徑：在多種路徑中，選擇最短、花費成本最小的路徑。應用於 GPS ( Global Positioning System ) 計算各種交通工具的路徑選擇
• 搜尋理論 ：如 Google 提供的搜尋引擎 ( Searching Engine )，使用者在搜尋時，系統會依照不同的搜尋理論排列資料

演算法

• 資料結構 + 演算法 = 可執行的程式

定義

• 在有限步驟內，解決數學問題的一個程序
• 為了解決特定問題，需要的有限機械性或重複性指令

條件

1. 輸入 ( Input ) ：零或多個清楚描述的資料
2. 輸出 ( Output ) ：至少要有一個輸出結果
3. 明確性 ( Definiteness )：每個指令跟步驟都要明確的
4. 有限性 ( Finiteness )：有限步驟後會結束，不能是無窮迴圈
5. 有效性 ( Effectiveness )：步驟是清楚且可行的，可以使用紙筆計算出答案

常見的演算法

• 分冶演算法 ( Divide and Conquer )：把複雜的大問題切成多個子問題，再一一解決
• 遞迴演算法 ( Recursion )：反覆呼叫自身的函數做計算，直到中止條件被觸發
• 疊代演算法 ( Iterative )：無法一次用公式來得到解，得用迴圈重複程式碼的某段程式碼才能求出解
• 枚舉演算法 / 窮舉法 ( Enumerative )：把全部可能的解答都列出來，適用範圍較小的問題
• 貪心演算法 ( Greedy Algorithm )：在每個步驟都採用當下狀態最有利最佳的選擇，希望從每個局部的最佳解，讓整體的結果也是最佳的

程式設計

評估程式語言

• 可讀性 ( Readability )：容易理解跟閱讀
• 平均成本低：編碼、執行、編譯、維護、學習、除錯、更新版本的成本
• 可靠度高：程式碼穩定，不易產生邊際錯誤 ( Side Effect )
• 可撰寫性高：相對容易撰寫

開發流程

需求認識 ( Requirements ) ⇒ 設計規劃 ( Design and Plan ) ⇒ 分析討論 ( Analysis ) ⇒ 編寫程式 ( Coding ) ⇒ 測試檢驗 ( Verification )

結構化程式設計

主要有兩種程式設計方法：

1. 由上而下：把整個程式由大到小拆分成 模組 ( Module ) 給程式設計師分別開發
2. 由下而上：程式設計師先完成整個程式中最簡單的部分，再慢慢完成其他部分

物件導向程式設計 ( Object-Oriented Programming, OOP )

物件有 「內部狀態 ( 屬性 ) 」 跟 「外部行為」 ，像是一台車的屬性可以是紅色烤漆、兩人坐，外部行為是行駛、剎車、按喇叭。OOP 把程式看成獨立的物件，提升程式的可讀性、重複使用性、延伸性。此外，OOP 設計還具備了以下三大重要的特性。

封裝 ( Encapsulation )

創造物件時會用類別 ( Class ) 來實現 ADT，可以把類別當成創造物件的設計圖，而依照設計圖創造出來的物件被稱為實體 ( Instance )。

ADT 的「抽象化」指的是把物件的特徵資料隱藏起來，只提供方法 ( Method ) 作為介面讓使用者操作，這種讓使用者無法直接操作資料的方式也稱資訊隱藏 ( Information Hiding )。封裝即是將資料與方法綁定，並做資訊隱藏，這樣做可保護資料的安全，防止外部程式修改物件的內部狀態，並提高程式的維護性。

繼承 ( Inheritance )

讓新創造的類別可以繼承既有類別的屬性與方法，並且能再添加不同的屬性跟方法到新類別中。如「跑車」可繼承「汽車」類別的行駛方法，再擴充超強貼背感的新屬性！

多形 ( Polymorphism )

讓一樣名稱的方法再不同類別有不一樣的實現方式，像是「休旅車」跟「跑車」類別都繼承「汽車」類別，但兩者的「行駛」方法可以調整成不同的實現方法。

演算法效能分析

評估一個演算法的好壞可用 「空間複雜度（Space Complexity）」 跟 「時間複雜度（Time Complexity）」，前者指該演算法需要的固定 + 變動空間記憶體，後者指演算法需要的時間，目前主要是用時間複雜度來評估演算法。但每一台電腦的硬體條件都不同，導致同一演算法在不同的機器執行的時間都不一樣，因此用概量的方式來評估演算法的時間複雜度。

Big-O

表示一個演算法最壞的執行時間 ( Worse Case Executing Time ) 。

• 若則存在兩正數 c 跟 n0，讓 f(n) ≤ c * g(n)，且所有 n ≥ n0，則 f(n) = O (g(n))

• 判斷一個函式的 Big-O 是多少的方式：看最大的 n 是多少次方

  • 若 f(n)=2n+5，f(n)=O(n)
  • 若 f(n)=n^3+2n+5，f(n)=O(n^3)

• 找 c 跟 n0

  • c 是 f(n) 最大項的值再 +1；n0 再從 c 去推倒即可
  • f(n)=2n+5，f(n)=O(n)
    • c=3
    • n0 ≥ 5
      • f(n) ≤ c * g(n) ⇒ 2n + 5 ≤ 3n

Omega ( Ω )

表示一個演算法最好的執行時間。

• 若則存在兩正數 c 跟 n0，讓 f(n) ≥ c * g(n)，且所有 n ≥ n0，則 f(n) = Ω (g(n))

• 判斷一個函式的 Ω 是多少的方式：看最大的 n 是多少次方

  • 若 f(n)=2n+5，f(n)=Ω (n)
  • 若 f(n)=n^3+2n+5，f(n)=Ω (n^3)

• 找 c 跟 n0

  • c 是 f(n) 最大項的值；n0 再從 c 去推倒即可
  • f(n)=2n+5，f(n)=O(n)
    • c=2
    • n0 可以是任何數
      • f(n) ≥ c * g(n) ⇒ 2n + 5 ≥ 2n

Theta ( θ )

比 Big-O 跟 Ω 更精確，θ 是上述兩者的夾集。

• 若則存在三正數 c1、 c2 跟 n0，讓 c1*g(n)≤f(n) ≤ c2 * g(n)，且所有 n ≥ n0，則 f(n) = θ(g(n))

• 找 c1、 c2 跟 n0
  • f(n)=2n+5，f(n)=θ(n)
    • c1=2
    • c2=3
    • n0=5